package com.algorithm.learning.base.二叉树;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/24 23:43
 **/
public class 输出所有符合路径和的路径集合 {

    /**
     * 获取是否存在路径和的路径集合
     * @see 是否有路径和 从这里我们知道，路径和的意思
     *
     * 但是这道题要求输出符合的所有路径的集合，所以返回结果是集合套集合
     *
     * 例如：
     *           1
     *        ↙     ↘
     *       2       4
     *     ↙  ↘     ↙ ↘
     *    9   3   5   7
     * 目标值为12
     *
     * 那么输出的结果就是
     * [[1,2,9], [1,4,7]]
     * @param root
     * @param sum
     * @return
     */
    public static List<List<Integer>> pathSumList(TreeNode root, int sum) {
        if (root == null) {
            return null;
        }
        List<List<Integer>> result = new ArrayList<>();

         doPathSumList(root, result, new ArrayList<>(), 0, sum);
         return result;
    }

    private static void doPathSumList(TreeNode node, List<List<Integer>> result, List<Integer> curPath, int curNum, int sum) {
        if (node.left == null && node.right == null) {
            curNum += node.value;
            if (curNum == sum) {
                curPath.add(node.value);
                result.add(copy(curPath));
                // 清理现场
                // 这里一定要remove掉最后一个数，因为我们知道，递归结束后，还需要往上层返回，如果此时还有右子树的话，那么curPath中的数据一定会多一个叶子节点
                curPath.remove(curPath.size() - 1);
            }
        }

        curNum += node.value;
        curPath.add(node.value);
        if (node.left != null) {
             doPathSumList(node.left, result, curPath, curNum, sum);
        }

        if (node.right != null) {
             doPathSumList(node.right, result, curPath, curNum, sum);
        }
        // 这里也需要清理现场
        // 如果当前路径不满足结果，那么还需要网上掉，所以还需要把当前路径中的最后一个数移除掉
        curPath.remove(curPath.size() - 1);
    }

    private static List<Integer> copy(List<Integer> list) {
        return new ArrayList<>(list);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(4);
        root.left.left = new TreeNode(9);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        System.out.println(pathSumList(root, 12));
    }
}
